package Exams.TianChi;

public class q2 {
    int m, n;
    int[] res;
    public int[] observingPeriodicity(int[] record, int[] robot) {
        m = record.length;
        n = robot.length;
        res = new int[n];
        backtrack(0, record, robot);
        return res;
    }

    public boolean backtrack(int robotIndex, int[] record, int[] robot) {
        if (robotIndex == n) {
            for (int i = 0; i < m; i++) {
                if (record[i] != 0) {
                    return false;
                }
            }
            return true;
        }
        int maxPeriod = m - robot[robotIndex];
        for (int i = 1; i <= maxPeriod; i++) {
            boolean flag = true;
            for (int j = robot[robotIndex]; j < m; j += i) {
                if (record[j] == 0) {
                    flag = false;
                    break;
                }
            }
            if (!flag) {
                continue;
            }
            for (int j = robot[robotIndex]; j < m; j += i) {
                record[j]--;
            }
            res[robotIndex] = i;
            if (backtrack(robotIndex + 1, record, robot)) {
                return true;
            }
            for (int j = robot[robotIndex]; j < m; j += i) {
                record[j]++;
            }
        }
        return false;
    }
}
